#include "common.hpp"
typedef void (*func)(size_t * ds, size_t count);

void test_sort(func f)
{
   size_t c = 10;
   size_t ds[c];
   size_t i = 0;
   while (i != c)
     {
       ds[i] = i;
       ++i;
     }
   f(ds, c);
   while(i != 1)
     {
       EXPECT_LE(ds[c - i + 1], ds[c - i]);
       --i;
     } 
}

void bubble(size_t* datas, size_t count)
 {
   for (size_t i = 0; i < count; ++i)
     {
       const size_t& end = count - i;
       for (size_t j = 1; j < end; ++j)
	 {
	   if (datas[j - 1] < datas[j])
	     {
	       datas[j] = datas[j] + datas[j - 1];
	       datas[j - 1] = datas[j] - datas[j - 1];
	       datas[j] =  datas[j] - datas[j - 1];
	     }
	 }
     }
 }

void select(size_t* ds, size_t count)
{
  for (size_t i = 0; i < count; ++i)
    {
      size_t* min = &ds[i];
      for (size_t j = i; j < count; ++j)
	{
	  if (ds[j] < *min)
	    {
	      min = &ds[j];
	    }
	}
      *min = ds[i] + *min;
      ds[i] = *min - ds[i];
      *min = *min - ds[i];
    }
}

void insert(size_t* ds, size_t count)
{
  for (size_t i = 0; i < count; ++i)
    {
      for (size_t j = 0; j < i; ++j)
	{
	  if (ds[i] > ds[j])
	    {
	      ds[i] = ds[j] + ds[i];
	      ds[j] = ds[i] - ds[j];
	      ds[i] = ds[i] - ds[j];
	    }
	}
    }
}

//merge=> link list

void swap(size_t* ds, size_t i, size_t j)
{
  if (i == j)
   {
     return;  
   }
  ds[i] = ds[i] + ds[j];
  ds[j] = ds[i] - ds[j];
  ds[i] = ds[i] - ds[j];
   
}
void partition(size_t* ds, size_t l, size_t r)
{
  if (l >= r)
    {
      return;
    }
  swap(ds, l, (l + r) / 2);
  
  size_t last = l;
  for (size_t j = l + 1; j <= r; ++j)
    {
      if (ds[j] > ds[l])
	{
	  swap(ds, ++last, j);
	}
    }
  swap(ds, l, last);  
 if (last != l)
    {
      partition(ds, l, last - 1);
    }
  partition(ds, last + 1, r);
}

void quick(size_t* ds, size_t count)
{
  partition(ds, 0, count - 1);
}

TEST(sort, bubble)
{
  test_sort(bubble);
}

TEST(sort, select)
{
  test_sort(select);
}

TEST(sort, insert)
{
  test_sort(insert);
}

TEST(sort, quick)
{
  test_sort(quick);
}
